/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package phd.dupenois.changeidentifiers.algorithms.chihull;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.Set;
import java.util.TreeSet;
import uk.co.dupenois.geometry.Coordinate;
import uk.co.dupenois.geometry.Edge;


/**
 * Data structure to hold delaunay triangles, used
 * so we can hold information like current lowest vertex
 * @author mpd209
 */
public class DelaunayTriangulation {
    private ArrayList<DelaunayTriangle> masterListOfTriangles;
    private Hashtable<Edge, ArrayList<DelaunayTriangle>> edgeToTriangles;
    private Hashtable<Coordinate, ArrayList<Edge>> vertexToEdge;

    //HERE GOING TO NEED SOME MAPS KEEPING LEFT AND RIGHT CONSISTENT
    private TreeSet<Edge> leftToRightEdgeList;
    private TreeSet<Edge> rightToLeftEdgeList;

    private Coordinate currentLowestVertexLeft;
    private DelaunayTriangle currentLowestTriangleLeft;
    private Coordinate currentLowestVertexRight;
    private DelaunayTriangle currentLowestTriangleRight;


    public DelaunayTriangulation(){
        masterListOfTriangles = new ArrayList<DelaunayTriangle>();
        edgeToTriangles = new Hashtable<Edge, ArrayList<DelaunayTriangle>>();
        vertexToEdge = new Hashtable<Coordinate, ArrayList<Edge>>();
        rightToLeftEdgeList = new TreeSet<Edge>(Edge.ComparatorCoordinatesMaxXMinY);

        leftToRightEdgeList = new TreeSet<Edge>(Edge.ComparatorCoordinatesMinXMinY);
    }
    public void addTriangulation(DelaunayTriangulation triangulation){
//        long triangleTimer = System.currentTimeMillis();
        DelaunayTriangle[] newTriangles = triangulation.getTriangles();
//        int addCount = 0;
        for(DelaunayTriangle triangle : newTriangles){
            if(!masterListOfTriangles.contains(triangle)){
                this.addTriangle(triangle);
//                addCount++;
            }
        }
//        triangleTimer = System.currentTimeMillis()-triangleTimer;
//        if(triangleTimer>50) System.out.println("Added "+addCount+" triangles, took: "+triangleTimer+" ms");

    }
    public void addTriangle(DelaunayTriangle triangle){
//        long triangleTimer = System.currentTimeMillis();
//        long totalTriangleTimer = System.currentTimeMillis();
//        String triangleTimerOut = "\t**ADD**\n";
        if(getCurrentLowestTriangleLeft()==null){
            this.currentLowestTriangleLeft = triangle;
            this.currentLowestVertexLeft = triangle.getVertexMinYMinX();

        }else{
            if(triangle.compareByMinYMinX(this.currentLowestTriangleLeft)<0){
                this.currentLowestTriangleLeft = triangle;
                this.currentLowestVertexLeft = triangle.getVertexMinYMinX();
            }
        }
        if(getCurrentLowestTriangleRight()==null){
            this.currentLowestTriangleRight = triangle;
            this.currentLowestVertexRight = triangle.getVertexMinYMaxX();
//            if(this.currentLowestVertexRight.equalsCheck(new Coordinate(100.0, 100.0))){
//                System.out.println("\nInitialising "+this.currentLowestVertexRight+" as lowest right\n");
//                try {Thread.sleep(2000); } catch (InterruptedException ex) {}
//            }
        }else{
            if(triangle.compareByMinYMaxX(this.currentLowestTriangleRight)<0){
                this.currentLowestTriangleRight = triangle;
                this.currentLowestVertexRight = triangle.getVertexMinYMaxX();
//                if(this.currentLowestVertexRight.equalsCheck(new Coordinate(100.0, 100.0))){
//                    System.out.println("\nSetting "+this.currentLowestVertexRight+" as lowest right\n");
//                    try {Thread.sleep(2000); } catch (InterruptedException ex) {}
//                }
            }
        }
//        triangleTimer = System.currentTimeMillis()-triangleTimer;
//        triangleTimerOut += "\tSorting Minimums: "+triangleTimer+" ms\n";
//        triangleTimer = System.currentTimeMillis();
        //Add adjacent triangles
        Edge[] edges = triangle.getEdges();
        ArrayList<DelaunayTriangle> triangleList;
        Edge edgeReverse;
        boolean edgeExists = false;
        //Maximum of 3

        for(Edge edge : edges){
            edgeExists = false;
            edgeReverse = new Edge(edge.getFinish(), edge.getStart());
            
            if(edgeToTriangles.containsKey(edge)){
                edgeExists = true;
            }else if(edgeToTriangles.containsKey(edgeReverse)){
                edgeExists = true;
                edge = edgeReverse;
            }
            if(edgeExists){
                triangleList = edgeToTriangles.get(edge);
                //Maximum of 2, probably one
                for(DelaunayTriangle tri : triangleList){
                    tri.addAdjacent(triangle);
                    triangle.addAdjacent(tri);
                }
                triangleList.add(triangle);
            }else{
                triangleList = new ArrayList<DelaunayTriangle>();
                triangleList.add(triangle);
                edgeToTriangles.put(edge, triangleList);
                leftToRightEdgeList.add(edge);
                rightToLeftEdgeList.add(edge);
            }
            addVertexToEdgesEntry(edge.getStart(), edge);
            addVertexToEdgesEntry(edge.getFinish(), edge);
        }
//        triangleTimer = System.currentTimeMillis()-triangleTimer;
//        triangleTimerOut += "\tAdding Edges: "+triangleTimer+" ms\n";
//        triangleTimer = System.currentTimeMillis()-totalTriangleTimer;
//        if(triangleTimer>1) System.out.println(triangleTimerOut+"\tTotal time for add: "+triangleTimer+"ms\n");
        this.masterListOfTriangles.add(triangle);
        
    }


    private void addVertexToEdgesEntry(Coordinate vertex, Edge edge){
        if(vertexToEdge.containsKey(vertex)&& 
                !vertexToEdge.get(vertex).contains(edge)){
            vertexToEdge.get(vertex).add(edge);
        }else if(!vertexToEdge.containsKey(vertex)){
            vertexToEdge.put(vertex, new ArrayList<Edge>());
            vertexToEdge.get(vertex).add(edge);
        }
    }
     private void removeVertexToEdgesEntry(Coordinate vertex, Edge edge){
        if(vertexToEdge.containsKey(vertex)&&
                vertexToEdge.get(vertex).contains(edge)){
            vertexToEdge.get(vertex).remove(edge);
            if(vertexToEdge.get(vertex).isEmpty()){
                //Unlikely but possibly need to remove vertex
                vertexToEdge.remove(vertex);
            }
        }
    }
    public Coordinate[] getCoordinates(){
        return vertexToEdge.keySet().toArray(new Coordinate[vertexToEdge.size()]);
    }

    public Coordinate[] getCoordinatesAttachedTo(Coordinate vertex){
        Edge[] edges  = getEdgesByVertex(vertex);
        ArrayList<Coordinate> coords = new ArrayList<Coordinate>();
        Coordinate start;
        Coordinate finish;
        for(Edge edge : edges){
            start = edge.getStart();
            finish = edge.getFinish();
            if(!coords.contains(start)&&!vertex.equals(start)) coords.add(start);
            if(!coords.contains(finish)&&!vertex.equals(finish)) coords.add(finish);
        }
        return coords.toArray(new Coordinate[coords.size()]);
    }

    public void removeEdge(Edge edge){
        DelaunayTriangle[] triangles = getTrianglesByEdge(edge);
//        System.out.println(triangles.length+" Triangles found with edge: "+edge.getStart()+"->"+edge.getFinish());
//        ArrayList<DelaunayTriangle> trianglesToRemove = new ArrayList<DelaunayTriangle>();
        for(DelaunayTriangle triangle : triangles){
            removeTriangle(triangle);
//            if(!trianglesToRemove.contains(triangle)) trianglesToRemove.add(triangle);
        }
//        for(DelaunayTriangle triangle : trianglesToRemove){
//            removeTriangle(triangle);
//        }
    }

    public void removeTriangle(DelaunayTriangle triangle){
        Edge[] edges = triangle.getEdges();
        ArrayList<DelaunayTriangle> triangleList;
        Edge edgeReverse;
        boolean edgeExists = false;
        for(Edge edge : edges){
            edgeExists = false;
            edgeReverse = new Edge(edge.getFinish(), edge.getStart());
            if(edgeToTriangles.containsKey(edge)){
                edgeExists = true;
            }else if(edgeToTriangles.containsKey(edgeReverse)){
                edgeExists = true;
                edge = edgeReverse;
            }
            if(edgeExists){
                triangleList = edgeToTriangles.get(edge);
                for(DelaunayTriangle tri : triangleList){
                    if(!tri.equals(triangle)) tri.removeAdjacent(triangle);
                }
                triangleList.remove(triangle);
                if(triangleList.isEmpty()){
                    //Remove edge as well as edge no longer corresponds to
                    //any triangles
                    removeVertexToEdgesEntry(edge.getStart(), edge);
                    removeVertexToEdgesEntry(edge.getFinish(), edge);
                    edgeToTriangles.remove(edge);
                    leftToRightEdgeList.remove(edge);
                    rightToLeftEdgeList.remove(edge);
                }
            }
        }
        this.masterListOfTriangles.remove(triangle);
        if(this.masterListOfTriangles.size()>0){
            if(this.currentLowestTriangleLeft.equals(triangle)){
                Collections.sort(this.masterListOfTriangles, DelaunayTriangle.comparatorTrianglesByMinYMinX);
                this.currentLowestTriangleLeft = this.masterListOfTriangles.get(0);
                this.currentLowestVertexLeft = this.currentLowestTriangleLeft.getVertexMinYMinX();
            }
            if(this.currentLowestTriangleRight.equals(triangle)){
                Collections.sort(this.masterListOfTriangles, DelaunayTriangle.comparatorTrianglesByMinYMaxX);
                this.currentLowestTriangleRight = this.masterListOfTriangles.get(0);

                this.currentLowestVertexRight = this.currentLowestTriangleRight.getVertexMinYMaxX();
//                if(this.currentLowestVertexRight.equalsCheck(new Coordinate(100.0, 100.0))){
//                    System.out.println("\nRemoval Setting "+this.currentLowestTriangleRight+" as lowest right triangle\n");
//                    System.out.println("\nRemoval Setting "+this.currentLowestVertexRight+" as lowest right\n");
//                    try {Thread.sleep(2000); } catch (InterruptedException ex) {}
//                }
            }
        }else{
            this.currentLowestTriangleLeft = null;
            this.currentLowestVertexLeft = null;
            this.currentLowestTriangleRight = null;
            this.currentLowestVertexRight = null;
        }
        
    }

    public Edge[] getEdgesLeftToRight(){
        return leftToRightEdgeList.toArray(new Edge[leftToRightEdgeList.size()]);
    }

    public Edge[] getEdgesRightToLeft(){
        return rightToLeftEdgeList.toArray(new Edge[rightToLeftEdgeList.size()]);
    }

//    public Edge[] getEdgesLeftToRight(){
//        Set<Edge> edges = edgeToTriangles.keySet();
//        Edge[] edgeArray = edges.toArray(new Edge[edges.size()]);
//        return sortEdgesLeftToRight(edgeArray);
//    }
//
//    public Edge[] getEdgesRightToLeft(){
//        Set<Edge> edges = edgeToTriangles.keySet();
//        Edge[] edgeArray = edges.toArray(new Edge[edges.size()]);
//        return sortEdgesRightToLeft(edgeArray);
//    }
//    private Edge[] sortEdgesRightToLeft(Edge[] edges){
//        Arrays.sort(edges, new Comparator<Edge>(){
//            public int compare(Edge arg0, Edge arg1) {
//                double diff = (arg1.getRightCoordinate().getX()-arg0.getRightCoordinate().getX());
//                if(diff<0) return -1;
//                if(diff==0) return 0;
//                return 1;
//            }
//        });
//        return edges;
//    }
//    private Edge[] sortEdgesLeftToRight(Edge[] edges){
//        Arrays.sort(edges, new Comparator<Edge>(){
//            public int compare(Edge arg0, Edge arg1) {
//                double diff = (arg0.getLeftCoordinate().getX()-arg1.getLeftCoordinate().getX());
//                if(diff<0) return -1;
//                if(diff==0) return 0;
//                return 1;
//            }
//
//        });
//        return edges;
//    }
    public Edge[] getEdgesByVertex(Coordinate vertex){
        Edge[] edges = new Edge[0];
        if(vertexToEdge.containsKey(vertex)){
            ArrayList<Edge> edgeList = vertexToEdge.get(vertex);
            edges = edgeList.toArray(new Edge[edgeList.size()]);
        }
        return edges;
    }

//    public Edge[] getEdgesByVertexRightToLeft(Coordinate vertex){
//        Edge[] edges = getEdgesByVertex(vertex);
//        return sortEdgesRightToLeft(edges);
//    }
//    public Edge[] getEdgesByVertexLeftToRight(Coordinate vertex){
//        Edge[] edges = getEdgesByVertex(vertex);
//        return sortEdgesLeftToRight(edges);
//    }

    public DelaunayTriangle[] getTriangles(){
        return this.masterListOfTriangles.toArray(new DelaunayTriangle[this.masterListOfTriangles.size()]);
    }




    /**
     * @return the currentLowestVertex
     */
    public Coordinate getCurrentLowestVertexLeft() {
        return currentLowestVertexLeft;
    }

    /**
     * @return the currentLowestTriangle
     */
    public DelaunayTriangle getCurrentLowestTriangleLeft() {
        return currentLowestTriangleLeft;
    }
    /**
     * @return the currentLowestVertexRight
     */
    public Coordinate getCurrentLowestVertexRight() {
        return currentLowestVertexRight;
    }

    /**
     * @return the currentLowestTriangleRight
     */
    public DelaunayTriangle getCurrentLowestTriangleRight() {
        return currentLowestTriangleRight;
    }
    
    public DelaunayTriangle[] getTrianglesByEdge(Edge edge){
        if(!edgeToTriangles.containsKey(edge)){
            edge = new Edge(edge.getFinish(), edge.getStart());
            if(!edgeToTriangles.containsKey(edge)){
                return new DelaunayTriangle[0];
            }
        }
        ArrayList<DelaunayTriangle> triangleList = edgeToTriangles.get(edge);
        return triangleList.toArray(new DelaunayTriangle[triangleList.size()]);
        
    }

    public void printEdges(){
        System.out.println("EDGE LIST:-");
        for(Edge edge : getEdgesLeftToRight()){
            System.out.println(""+edge.getStart()+"->"+edge.getFinish());
        }
    }
    
    
}
